1. Field of the Invention
The present invention relates to an error correction system, and more particularly to an n error correction system using an n-1 correction method and apparatus.
2. Description of the Related Art
Generally, an error correction apparatus is applied to a digital communication system or a digital storage system, and can correct errors generated in the data to be received or reproduced.
Methods, for example, are known for correcting errors in a block of data. Hardware for correcting n-1 errors is capable of correcting n errors by repeated execution. For instance, triple error correction is made possible using two kinds of error correction hardware by repetition.
FIG. 1 is a block diagram illustrating a contemporary dual error correction system. A first coefficient operating circuit 1 receives syndromes S.sub.0, S.sub.1, S.sub.2 and S.sub.3 and generates two error correction polynomials .sigma..sub.1 .sigma..sub.2. A second coefficient operating circuit 2 receives the two error correction polynomials .sigma..sub.1 .sigma..sub.2 and generates a coefficient K. A third coefficient operating circuit 3 receives the coefficient K and generates a coefficient vector .chi..sub.1. An error location value operating circuit 4 receives the coefficient .chi..sub.1 and generates two error locations X.sup.1 and X.sup.2. An error value operation circuit 5 receives the two error locations X.sup.1 and X.sup.2 and generates two error values .gamma..sub.1 and .gamma..sub.2. An adder 6 receives the two error values .gamma..sub.1 and .gamma..sub.2 and syndrome S.sub.0 and generates a signal e.sub.k that is the corrected sequence.
The two error correction polynomials .alpha..sigma..sub.1 and .sigma..sub.2 are generated by calculating the following two equations: ##EQU2## where .sigma..sub.1 and .sigma..sub.2 are error correction polynomials.
a second coefficient calculating circuit 2 for receiving the error correction polynomials .sigma..sub.1 and .sigma..sub.2 to calculate a coefficient K as .sigma..sub.2 divided by .sigma..sub.1.sup.2 ;
an X.sub.1 calculating circuit 3 for operating an X.sub.1 value satisfying EQU X.sub.0 =k.sub.3 +k.sub.5 +k.sub.6 EQU X.sub.1 =k.sub.0 +k.sub.2 +k.sub.4 EQU X.sub.2 =k.sub.0 +k.sub.3 +k.sub.4 EQU X.sub.3 =k.sub.1 +k.sub.2 +k.sub.3 +k.sub.4 EQU X.sub.4 =k.sub.0 +k.sub.7 EQU X.sub.5 =k.sub.1 +k.sub.2 +k.sub.3 +k.sub.4 +k.sub.6 EQU X.sub.6 =k.sub.0 +k.sub.1 +k.sub.2 +k.sub.4 +k.sub.7 EQU X.sub.7 =k.sub.0 +k.sub.1 +k.sub.2 +k.sub.4
using the coefficient K (here, each symbol "+" represents an XOR operation);
an error location value operation circuit 4 for calculating EQU X.sub.1 =X1.multidot..sigma..sub.1 EQU X.sub.2 =(1+X.sub.1).multidot..pi..sub.1 PA1 an error value operation circuit 5 for receiving the error locations X.sub.1 and X.sub.2 to calculate ##EQU3## where .gamma..sub.1 and .gamma..sub.2 are error values. (The above description is disclosed in U.S. Pat. No. 5,315,601 and is expressly incorporated by reference).
using the X.sub.1 value, where X.sub.1 and X.sub.2 are error locations and; and .multidot. is a multiplying operation.
FIG. 2 illustrates a detailed structure of the third coefficient operation circuit of FIG. 1, showing thirteen XOR gates which satisfy the aforementioned equations.
It should be noted that the system of the present invention is applicable to various dual error correction systems, and not restricted to the above-described dual error correction system.
The n error correction algorithm using the n-1 error correction system will be described below.
For n error correction, the Reed-Solomon code requires n error values and 2n syndrome equations for seeking n error locations.
First, in order to obtain 2n-2 syndromes for n-1 error correction, 2n-1 syndromes are obtained for n error correction from the following equation: EQU S.sub.0 =e.sub.1 +e.sub.2 e.sub.3 + . . . +e.sub.n ##EQU4##
In the above equations, e.sub.i represents the error value and x.sub.i represent the error location.
To eliminate e.sub.n and x.sub.n from equation 1, in the Galois Field GF(2.sup.8), which is a field of 256 eight bit binary bytes, if x.sub.1 =.alpha..sup.B1, X.sub.2 =.alpha..sup.B2, X.sub.3 =.alpha..sup.B3, X.sub.4 =.alpha..sup.B4, and supposing S.sub.K ', =S.sub.K+1 /.alpha..sup.n+1 (where K=0, 1 . . . , 2n-1; B is a primitive element of GF(2.sup.8); .alpha. is an element of the field GF(2.sup.8)), the equations S.sub.0, S.sub.1 . . . , S.sub.2n-2 are transformed as follows: ##EQU5## Here, .alpha..sup..beta.N+1 is an assumed error location and indicates .alpha..sub.k of FIG. 3.
If we define ##EQU6## where i is an integer greater than zero, the equations are transformed as ##EQU7## From the syndrome transform alogrithm, we get EQU S.sub.0 '=e.sub.1 ''e.sub.2 ' EQU S.sub.1 '=e.sub.1 '.alpha..sup..beta.1 +e.sub.2 '.alpha..sup..beta.2 EQU S.sub.2 '=e.sub.1 '.alpha..sup.2.beta.1 +e.sub.2 '.alpha..sup.2.beta.2 EQU S.sub.3 '=e.sub.1 '.alpha..sup.3.beta.1 .alpha.e.sub.2 '.alpha..sup.3.beta.2
when supposing S.sub.i.sup./ =S.sub.i +S.sub.i+1 /.alpha..sup..beta.3 and e.sub.i '=e.sub.i (1+.alpha..sup..beta.i /.alpha..sup..beta.3)
where i is an integer greater than zero. Here, the dual error correction is repeated until successful, so as to obtain two error locations and two error values. Finally, a third error value and error location area obtained using S.sub.0 and S.sub.1.
An example of the triple error correction using the dual error correction algorithm uses a Reed Solomon Code. If an exact code word C(s)=0 and a received code word r(x)=.alpha.x+.alpha.x.sup.5 +.alpha.x.sup.6, which consists of parity check digits and information digits, then EQU S.sub.0 =.alpha.+.alpha..sup.3 +.alpha..sup.4 =.alpha..sup.105 EQU S.sub.1 =.alpha..multidot..alpha.+.alpha..sup.3 .multidot..alpha..sup.5 +.alpha..sup.4 .multidot..alpha..sup.6 =.alpha..sup.133 EQU S.sub.2 =.alpha..multidot..alpha..sup.2 +.alpha..sup.3 .multidot..alpha..sup.10 .alpha..sup.4 .multidot..alpha..sup.12 =.alpha..sup.216 EQU S.sub.3 =.alpha..multidot..alpha..sup.3 +.alpha.3.multidot..alpha..sup.15 +.alpha..sup.4 .multidot..alpha..sup.18 =.alpha..sup.170 EQU S.sub.4 =.alpha..multidot..alpha..sup.4 +.alpha..sup.3 .multidot..alpha..sup.20 +.alpha..sup.4 .multidot..alpha..sup.24 =.alpha..sup.174
Here, let's suppose .alpha.=.alpha..sup.6. (If .alpha..notident..alpha..sup.6, the dual error correction is carried out.) Then, EQU S.sub.0 '=S.sub.0 +S.sub.1 /.alpha..sup.6 =.alpha..sup.85 EQU S.sub.1 '=S.sub.1 +S.sub.2 /.alpha..sup.6 =.alpha..sup.106 EQU S.sub.2 '=S.sub.2 +S.sub.3 /.alpha..sup.6 =.alpha..sup.50 EQU S.sub.3 '=S.sub.3 +S.sub.4 /.alpha..sup.6 =.alpha..sup.218
If the dual error correction is performed using S.sub.0 ', S.sub.1 ', S.sub.2 and S.sub.3 ', then e.sub.0 '=.alpha..sup.134, X.sub.1 =.alpha. and e.sub.1 '=.alpha..sup.27, x.sub.2 =.alpha..sup.5 are obtained, and thus, real error values e.sub.0 =e.sub.0 '/(1+.alpha./.alpha..sup.6)=.alpha. and e1=e1'/(1+.alpha..sup.5 /.alpha..sup.6)=.alpha..sup.3 are obtained, Then, the final error value is e.sub.2 =S.sub.0 +e.sub.0 +e.sub.1 =.alpha..sup.105 +.alpha.+.alpha..sup.3 =.alpha..sup.4 and the final error location is ##EQU8## Here, the assumed value .alpha.=.alpha..sup.6 is obvious.
As described above, the three error value .alpha., .alpha..sup.3 and .alpha..sup.4 and error locations .alpha., .alpha..sup.5 and .alpha..sup.6 can be precisely obtained. The above shows a method of which triple error correction is performed using the conventional dual error correction method.